翻訳と辞書
Words near each other
・ SpareBank 1 SR-Bank
・ SpareBank 1 Østfold Akershus
・ Sparebanken ABC
・ Sparebanken Hedmark
・ Sparebanken Møre
・ Sparebanken NOR
・ Sparebanken Nord-Norge
・ Sparebanken Nordvest
・ Spanner (surname)
・ Spanner Banner
・ Spanner barb
・ Spanner Films
・ Spanner Pretorius
・ Spanners (album)
・ Spanning
Spanning tree
・ Spanning tree (disambiguation)
・ Spanning Tree Protocol
・ Spannum
・ Spannuth Mill
・ Spano
・ Spano Island
・ Spano v. New York
・ Spanos
・ Spanova
・ SPANphos
・ Spansion
・ Spanska Siw
・ Spantax
・ Spantax Flight 275


Dictionary Lists
翻訳と辞書 辞書検索 [ 開発暫定版 ]
スポンサード リンク

Spanning tree : ウィキペディア英語版
Spanning tree

In the mathematical field of graph theory, a spanning tree ''T'' of an undirected graph ''G'' is a subgraph that includes all of the vertices of ''G'' that is a tree. In general, a graph may have several spanning trees, but a graph that is not connected will not contain a spanning tree (but see Spanning forests below). If all of the edges of ''G'' are also edges of a spanning tree ''T'' of ''G'', then ''G'' is a tree and is identical to ''T'' (that is, a tree has a unique spanning tree and it is itself).
==Applications==

Several pathfinding algorithms, including Dijkstra's algorithm and the A
* search algorithm
, internally build a spanning tree as an intermediate step in solving the problem.
In order to minimize the cost of power networks, wiring connections, piping, automatic speech recognition, etc., people often use algorithms that gradually build a spanning tree (or many such trees) as intermediate steps in the process of finding the minimum spanning tree.〔
R. L. Graham and Pavol Hell.
("On the History of the Minimum Spanning Tree Problem" ).
1985.

The Internet and many other telecommunications networks have transmission links that connect nodes together in a mesh topology that includes some loops.
In order to "avoid bridge loops and "routing loops", many routing protocols designed for such networks -- including the Spanning Tree Protocol, Open Shortest Path First, Link-state routing protocol, Augmented tree-based routing, etc. -- require each router to remember a spanning tree.

抄文引用元・出典: フリー百科事典『 ウィキペディア(Wikipedia)
ウィキペディアで「Spanning tree」の詳細全文を読む



スポンサード リンク
翻訳と辞書 : 翻訳のためのインターネットリソース

Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.